package ds.tree;

class TreeNode{
	int value;
	TreeNode left = null;
	TreeNode right = null;
	
	TreeNode(int val){
		this.value = val;
	}
	
	public String toString(){
		return String.valueOf(value);
	}
}
public class Traversal {

	public static void main(String[] args) {
		Traversal treeTraversal = new Traversal();
		System.out.println("In Order Traversal ");
		treeTraversal.inOrderTraversal(tree());
		System.out.println("\nPre Order Traversal = ");
		treeTraversal.preOrderTraversal( tree());
		System.out.println("\nPost Order Traversal = ");		
		treeTraversal.postOrderTraversal(tree());
	}
	
	/**
	 * traverse left sub tree
	 * visit the root
	 * traverse right sub tree
	 * 
	 * @param node
	 */
	public void inOrderTraversal(TreeNode node){
		if(node == null){
			return;
		}
		inOrderTraversal(node.left);
		System.out.print(node + " ");
		inOrderTraversal(node.right);
	}
	/**
	 * traverse left sub tree
	 * traverse right sub tree
	 * visit the root
	 * 
	 * @param node
	 */
	public void postOrderTraversal(TreeNode node) {
		if(node == null)
			return;
		postOrderTraversal(node.left);
		postOrderTraversal(node.right);
		System.out.print(node + " ");
	}
	/**
	 * visit the root
	 * traverse left sub tree
	 * traverse right sub tree
	 * 
	 * @param node
	 */
	public void preOrderTraversal(TreeNode node) {
		if(node == null){
			return;			
		}
		System.out.print(node + " ");
		preOrderTraversal(node.left);
		preOrderTraversal(node.right);
	}

	private static TreeNode tree(){
		TreeNode A = new TreeNode(1);
		TreeNode B = new TreeNode(2);
		TreeNode C = new TreeNode(3);
		TreeNode D = new TreeNode(4);
		TreeNode E = new TreeNode(5);
		
		A.left = B;
		A.right = C;
		B.left = D;
		B.right = E;
		
		return A;
	}
	
}
